#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>

using namespace std;

class Solution
{
public:
    string minWindow(string s, string t)
    {
        map<char, int> countMap;
        for (auto c : t)
        {
            if (countMap.find(c) == countMap.end())
                countMap[c] = 1;
            else
                countMap[c]++;
        }
        queue<int> roi;
        int right = 0;
        int minLeft = -1, minRight = -1, minLen = INT_MAX;
        while (right < s.size())
        {
            if (countMap.find(s[right]) != countMap.end())
            {
                char c = s[right];
                countMap[c]--;
                roi.push(right);
                // check char in map
                bool check = true;
                for (auto it = countMap.begin(); it != countMap.end(); it++)
                {
                    if (it->second > 0)
                    {
                        check = false;
                        break;
                    }
                }
                if (check)
                {
                    if (right - roi.front() < minLen)
                    {
                        minLen = right - roi.front();
                        minLeft = roi.front();
                        minRight = right;
                    }
                    // try to pop left
                    while (countMap[s[roi.front()]] < 0)
                    {
                        countMap[s[roi.front()]]++;
                        roi.pop();
                        if (right - roi.front() < minLen)
                        {
                            minLen = right - roi.front();
                            minLeft = roi.front();
                            minRight = right;
                        }
                        if (roi.front() > s.size())
                        {
                            cerr << "error" << endl;
                        }
                    }
                }
            }
            right++;
        }
        if (minLeft == -1 || minRight == -1)
            return "";
        return s.substr(minLeft, minLen + 1);
    }
};
int main()
{
    cout << "Code76" << endl;
    Solution s;
    string s1 = "wegdtzwabazduwwdysdetrrctotpcepalxdewzezbfewbabbseinxbqqplitpxtcwwhuyntbtzxwzyaufihclztckdwccpeyonumbpnuonsnnsjscrvpsqsftohvfnvtbphcgxyumqjzltspmphefzjypsvugqqjhzlnylhkdqmolggxvneaopadivzqnpzurmhpxqcaiqruwztroxtcnvhxqgndyozpcigzykbiaucyvwrjvknifufxducbkbsmlanllpunlyohwfsssiazeixhebipfcdqdrcqiwftutcrbxjthlulvttcvdtaiwqlnsdvqkrngvghupcbcwnaqiclnvnvtfihylcqwvderjllannflchdklqxidvbjdijrnbpkftbqgpttcagghkqucpcgmfrqqajdbynitrbzgwukyaqhmibpzfxmkoeaqnftnvegohfudbgbbyiqglhhqevcszdkokdbhjjvqqrvrxyvvgldtuljygmsircydhalrlgjeyfvxdstmfyhzjrxsfpcytabdcmwqvhuvmpssingpmnpvgmpletjzunewbamwiirwymqizwxlmojsbaehupiocnmenbcxjwujimthjtvvhenkettylcoppdveeycpuybekulvpgqzmgjrbdrmficwlxarxegrejvrejmvrfuenexojqdqyfmjeoacvjvzsrqycfuvmozzuypfpsvnzjxeazgvibubunzyuvugmvhguyojrlysvxwxxesfioiebidxdzfpumyon";
    string t1 = "ozgzyywxvtublcl";
    cout << s.minWindow(s1, t1) << endl;
    return 0;
}